//
// Created by shenbin on 2022/5/20.
// https://leetcode.cn/problems/redundant-connection/
//

#ifndef ALGORITHM_TRAINNING_C05_LC684_H
#define ALGORITHM_TRAINNING_C05_LC684_H

#include <vector>

using namespace std;

class LeetCode684 {
public:
    /**
     *
     * @param edges
     * [ [x, y], [x, y] ]
     * @return
     */
    vector<int> findRedundantConnection(vector<vector<int>> &edges) {
        n = 0;
        for (vector<int> &edge: edges) {
            int x = edge[0];
            int y = edge[1];
            n = max(n, max(x, y));
        }
        to = vector<vector<int>>(n + 1, vector<int>());
        visited = vector<bool>(n + 1, false);
        for (vector<int> &edge: edges) {
            int x = edge[0];
            int y = edge[1];
            // 出边数组加边
            to[x].push_back(y);
            to[y].push_back(x);
            hasCycle = false;
            for (int i = 1; i <= n; i++)visited[i] = false;
            dfs(x, 0);
            if (hasCycle) return edge;
        }
        return {};

    }

private:
    int n;
    vector<vector<int>> to;
    vector<bool> visited;
    bool hasCycle;

    // 图的深度优先遍历判断环的模板
    void dfs(int x, int fa) {
        visited[x] = true;
        // 出边数组访问x能到的周围点的方法
        for (int y: to[x]) {
            if (y == fa) continue;
            if (!visited[y]) dfs(y, x);
            else hasCycle = true;
        }
    }
};

#endif //ALGORITHM_TRAINNING_C05_LC684_H
